import random
import gmpy2


def divide_pq(e, d, n):
    k = e * d - 1
    while True:
        g = random.randint(2, n - 1)
        t = k
        while True:
            if t % 2 != 0:
                break
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gmpy2.gcd(x - 1, n) > 1:
                p = gmpy2.gcd(x - 1, n)
                return (p, n // p)


e = 28590331496425613818981991777617535857151582651120346436859967760844419275658771430821058722393674433618893115968176611013590439492663850993790177381059077045197086133940118402088554088073121591402095323966107722485647643452801806511583327361664114727935171402256611877627071996643841223356362367747555753013
n = 82016816963574560365976489524199243050120748716806912567895093731022264392235286524041630435256965141365061465268083316572087612155218061280174438822024011254230300135794845491207820824129566975766207833561478897150955561714805950254000266078855648956964973181825856857736088834707915779351726709234357344729
c = 0x1d1d98935d8bc395049b978b53ab72fc2c722f30b84bbf6c2bf3473320d040525bce59094840b229cf1fee0332c9dbcfc9cc07bf0841d2ec5f25b3f6a2868db433aca742d1e17a7b89f94412a77ea2f0ee3c30b53e250f77c44fd0e9c47bdfbfaa6dfe3f987409e9e6501962bf425cb686b570f922b843e30b4e96521c2dd296
d = 11883451304899715537
p, q = divide_pq(e, d, n)
print(f'p = {p}')
print(f'q = {q}')

p = 8281403040977025531549820722276265064745565654568438822912387430707467937623490534629221470348100185977195507167386055422519226694536400000080279834237671
q = 9903734494958037799680839753815171083006157728210189116724935884147895459864893196164405513869856559603118560765385175174916229249053756596318108626734399
